//
//  ProblemOffer40.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/13.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 40. 最小的k个数 ✅
 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

 示例 1：
     输入：arr = [3,2,1], k = 2
     输出：[1,2] 或者 [2,1]
 示例 2：
     输入：arr = [0,1,2,1], k = 1
     输出：[0]
 限制：
     0 <= k <= arr.length <= 10000
     0 <= arr[i] <= 10000
 */
@objcMembers class ProblemOffer40: NSObject {
    func solution() {
        let list = [5,2,1,4,9,5]
        print(getLeastNumbers(list, 3))
        
        let arr = [0,0,1,2,4,2,2,3,1,4]
        print(getLeastNumbers(arr, 8))
    }
    
    func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
        if k == 0 {
            return []
        }
        
        var list = arr
        return quicksort(&list, 0, arr.count-1, k-1)
    }
    
    // 使用快速排序的变种，只求出求K个的大小
    func quicksort(_ list: inout [Int], _ l: Int, _ r: Int, _ k: Int) -> [Int] {
        let index = getIndex(&list, l, r)
        if index == k {
            return Array(list[0...index])
        }
        
        return index < k ? quicksort(&list, index+1, r, k) : quicksort(&list, l, index-1, k)
    }
    
    
    /*
     快速排序
     */
    func sortQuick(_ list: inout [Int], _ l: Int, _ r: Int) {
        if l >= r {
            return
        }
        let index = getIndex(&list, l, r)
        
        print(index)
        print(list)
        
        // 递归
        sortQuick(&list, l, index-1)
        sortQuick(&list, index+1, r)
    }
    
    func getIndex(_ arr: inout [Int], _ l: Int, _ r: Int) -> Int {
        let t = arr[l]
        var left = l
        var right = r + 1
        
        while true {
            right -= 1
            while right > l && arr[right] > t {         // 找到第一个 < t 的位置
                right -= 1
            }
            left += 1
            while left < r && arr[left] < t {           // 找到第一个 >= t 的位置
                left += 1
            }
            
            if left >= right {
                break
            }
            
            let t = arr[left]
            arr[left] = arr[right]
            arr[right] = t
        }
        
        arr[l] = arr[right]
        arr[right] = t
        return right
    }
}
